package 真题;


/**
 * @author： li
 * @date： 2022-01-15 16:31
 * @version 1.0
 */

/*【问题描述】
下面的图形是著名的杨辉三角形:
如果我们按从上到下、从左到右的顺序把所有数排成一列，可以得到如下数列:
1，
1，1，
1，2,1，
1,3,3，1，
1，4,6，4，1，...
给定一个正整数N，请你输出数列中第一次出现N是在第几个数?
【输入格式】
输入一个整数N。
【输出格式】
输出一个整数代表答案。
【样例输入】
6
【样例输出】
13
对于20%的评测用例，1≤N ≤ 10;
对于所有评测用例，1<N≤1000000000。

 */
import java.util.Scanner;
public class 杨辉三角形_求N第一次出现位数_所有测试都可 {
    static long N;
    static long c(int a, int b)//求第i行第j列的值
    {
        long res = 1;
        for (long i = a, j = 1; j <= b; i--, j++) {
            res = res * i / j;
            if (res > N)//如果中间结果超过N就直接返回
                return res;
        }
        return res;
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        N = sc.nextInt();
        for (int k = 16; k >= 0; k--)//一列一列的找
        {
            long l = 2 * k, r = Math.max(N, l), mid = 0;
            while (l <= r) {//对第k列二分查找行
                mid = l + (r - l) / 2;//二分行
                long CC = c((int) mid, k);
                if (CC == N)
                    break;
                else if (CC > N)
                    r = mid - 1;
                else
                    l = mid + 1;
            }
            if (c((int) mid, k) == N) {//第mid行、第k列的数就是N
                System.out.println((mid + 1) * mid / 2 + k + 1);
                //杨辉三角形的行数符号公差为1的等差数列，故用等差数列求和公式
                //加上第几列再加上1（因为列从0开始）即可得出该数的位置
                break;
            }
        }

    }
}

